package chapter5.part9;

/**
 * @author zsh
 * @Description 删除整数的k个数字，获得删除后的最大值
 * @create 2022-04-21 19:48
 */
public class RemoveKDigits2 {
    /**
     * 删除整数的k个数字，获得删除后的最大值
     * @param num  原整数
     * @param k  删除数量
     */
    public static String removeKDigits(String num, int k) {
        int newLength = num.length() - k;
        char[] stack = new char[num.length()];

        int top = 0;

        for (int i = 0; i < num.length() ; i++){
            char c = num.charAt(i);

            //关键,循环判断，移除前面所有小于当前值的k个值
            while (top > 0 && stack[top-1] < c && k > 0){
                top--;
                k--;
            }
            stack[top++] = c;
        }

        // 用栈构建新的整数字符串
        return newLength<=0 ? "0" : new String(stack, 0, newLength);

    }

    public static void main(String[] args) {
        System.out.println(removeKDigits("1593212", 3));
        System.out.println(removeKDigits("30200", 1));
        System.out.println(removeKDigits("10", 2));
        System.out.println(removeKDigits("541270936", 3));
        System.out.println(removeKDigits("1593212", 4));
        System.out.println(removeKDigits("1000020000000010", 2));
    }
}
